#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "Graph.h"

inline static int archCmp(const void *e1, const void *e2) {
    const AdjacentMatrix::Arch * p1 = (const AdjacentMatrix::Arch *) e1, *p2 = (const AdjacentMatrix::Arch*) e2;
    return (p1->i < p2->i || (p1->i == p2->i && (p1->j < p2->j || (p1->j == p2->j && p1->w <= p2->w)))) ? -1 : 1;
}

void BaseGraph::allocateBuf() {
    result = (int*) malloc(sizeof(int) * n);
    assert(result!=NULL);
}

const int BaseGraph::RESULT_MAX_VALUE = 0x7fffffff;

BaseGraph::BaseGraph() :
        n(0), m(0), result(NULL) {
}

BaseGraph::BaseGraph(int n, int m) :
        n(n), m(m) {
    allocateBuf();
}

BaseGraph::~BaseGraph() {
    if (result != NULL) free(result);
}

int BaseGraph::checkSum() {
    assert(result!=NULL);
    int ret = 0;
    for (int i = 0; i < n; ++i)
        ret ^= result[i] + i;
    return ret;
}

void BaseGraph::resetResult() {
    for (int i = 0; i < n; ++i)
        result[i] = RESULT_MAX_VALUE;
}

void BaseGraph::showResult() {
    assert(result!=NULL);
    printf("n=%d m=%d\n", n, m);
    for (int i = 0; i < n; ++i)
        printf("%d ", result[i]);
    printf("\n");
}

void AdjacentMatrix::buildIndex() {
    memset(g, 0xff, sizeof(int) * (n + 1));
    for (int i = 0; i < m; ++i)
        if (g[archArray[i].i] == -1) g[archArray[i].i] = i;
    g[n] = m;
    for (int i = n - 1; i >= 0; --i)
        if (g[i] == -1) g[i] = g[i + 1];
}

void AdjacentMatrix::readFromTextFile(const char * const fileName) {
    FILE *fin = fopen(fileName, "r");

    char* ret;
    char buffer[0xff];
    do {
        ret = fgets(buffer, 0xff, fin);
        assert(ret!=NULL);
    } while (buffer[0] != 'p' && ret != NULL);
    sscanf(buffer, "p sp %d %d", &n, &m);
    BaseGraph::allocateBuf();

    allocateBuf();

    for (int i = 0; i < m; ++i) {
        do {
            ret = fgets(buffer, 0xff, fin);
            assert(ret!=NULL);
        } while (buffer[0] != 'a' && ret != NULL);
        sscanf(buffer, "a %d %d %d", &archArray[i].i, &archArray[i].j, &archArray[i].w);
        --archArray[i].i;
        --archArray[i].j;
    }

    fclose(fin);

    qsort(archArray, m, sizeof(Arch), archCmp);
    buildIndex();
}

void AdjacentMatrix::readFromObjectFile(const char * const fileName) {
    size_t ret;
    FILE *fin = fopen(fileName, "rb");
    ret = fread(&n, sizeof(n), 1, fin);
    assert(ret == 1);
    BaseGraph::allocateBuf();
    ret = fread(&m, sizeof(m), 1, fin);
    assert(ret == 1);
    assert(m >= 0);

    allocateBuf();
    ret = fread(archArray, sizeof(Arch), m, fin);
    assert(ret == (size_t )m);
    ret = fread(g, sizeof(int), n + 1, fin);
    assert(ret == (size_t )(n + 1));
    fclose(fin);
}

void AdjacentMatrix::allocateBuf() {
    char *buf = (char*) malloc(sizeof(Arch) * m + sizeof(int) * (n + 1));
    assert(buf!=NULL);
    archArray = (Arch*) buf;
    g = (int *) (buf + sizeof(Arch) * m);
}

void AdjacentMatrix::freeBuf() {
    if (archArray != NULL) {
        free(archArray);
        archArray = NULL;
        g = NULL;
    }
}

AdjacentMatrix::AdjacentMatrix(const char * const fileName) {
    int len = strlen(fileName);
    if (strcmp(fileName + len - 6, "obj.gr") == 0) {
        readFromObjectFile(fileName);
    } else {
        readFromTextFile(fileName);
    }
}

AdjacentMatrix::AdjacentMatrix(int n, int m, Arch *archArray) :
        BaseGraph(n, m) {
    allocateBuf();
    memcpy(this->archArray, archArray, sizeof(Arch) * m);
    qsort(this->archArray, m, sizeof(Arch), archCmp);
    buildIndex();
}

AdjacentMatrix::~AdjacentMatrix() {
    freeBuf();
}

void AdjacentMatrix::dumpToObjectFile(const char * const fileName) {
    FILE *fout = fopen(fileName, "wb");
    fwrite(&n, sizeof(n), 1, fout);
    fwrite(&m, sizeof(m), 1, fout);
    fwrite(archArray, sizeof(Arch), m, fout);
    fwrite(g, sizeof(int), n + 1, fout);
    fclose(fout);
}

AdjacentMatrix::Arch *AdjacentMatrix::getArchArray() {
    return &archArray[0];
}

void AdjacentMatrix::print() {
    printf("n=%d m=%d\n", n, m);
    for (int i = 0; i < n; ++i)
        for (int j = g[i]; j < g[i + 1]; ++j)
            printf("%d %d %d\n", i, archArray[j].j, archArray[j].w);
}

void CacheFriendlyAdjacentMatrix::allocateBuf() {
    char *buf = (char*) malloc(sizeof(int) * n * 2);
    assert(buf!=NULL);
    index = (int*) buf;
    rindex = (int*) (buf + sizeof(int) * n);
}

void CacheFriendlyAdjacentMatrix::freeBuf() {
    if (index != NULL) {
        free(index);
        index = NULL;
        rindex = NULL;
    }
}

CacheFriendlyAdjacentMatrix::CacheFriendlyAdjacentMatrix(const char * const fileName) :
        AdjacentMatrix(fileName), index(NULL), rindex(NULL) {
    allocateBuf();
}

CacheFriendlyAdjacentMatrix::CacheFriendlyAdjacentMatrix(int n, int m, Arch *archArray) :
        AdjacentMatrix(n, m, archArray), index(NULL), rindex(NULL) {
    allocateBuf();
}

CacheFriendlyAdjacentMatrix::~CacheFriendlyAdjacentMatrix() {
    freeBuf();
}
